/**
 * 19. 删除链表的倒数第 N 个结点
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
 * 给定一个链表，删除链表的倒数第 n 个结点，并返回链表的头结点。
 * 题目数据保证链表长度大于 n。
 * 示例 1：
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：(删除头节点)
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：(删除尾节点)
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 */
public class Solution19 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1. 创建一个虚拟头节点，它的 next 指向真正的头节点。
        //    这可以统一处理“删除头节点”这个边界情况。
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 2. 初始化快慢两个指针，都指向虚拟头节点。
        //    快指针 fast 用于探路，慢指针 slow 用于最终定位到被删节点的前一个节点。
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 3. 【第一步：拉开距离】
        //    让快指针 fast 先向前移动 n + 1 步。
        //    这样，fast 和 slow 之间就形成了一个 n 个节点的固定距离。
        //    （多走一步是为了让 slow 最终停在被删节点的前一个节点上）
        for (int i = 0; i <= n; i++) {
            // 如果在此过程中 fast 变为 null，说明链表长度小于 n，
            // 这是一个无效的输入（根据 LeetCode 题目约束，这种情况不会发生）。
            // 但健壮的代码可以加上判断。
            // if (fast == null) {
            //     return head; // 或者抛出异常
            // }
            fast = fast.next;
        }

        // 4. 【第二步：齐头并进】
        //    同时移动快慢指针，直到快指针 fast 到达链表的末尾 (null)。
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 5. 【执行删除】
        //    此时，slow 指针正好位于要被删除节点的前一个节点。
        //    执行删除操作，即让 slow 的 next 指针跳过被删节点。
        slow.next = slow.next.next;

        // 6. 返回新链表的头节点。
        //    注意：永远不要返回 head，因为 head 可能已经被删除了。
        //    返回 dummy.next 才能保证结果永远正确。
        return dummy.next;
    }
}